package com.zj.leetcode.medium.hash;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @program: algorithm
 * @description: 最长连续序列
 * 128 longest-consecutive-sequence
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class LongestConsecutiveSequence {
    public static void main(String[] args) {
//        int[] nums = {100, 4, 200, 1, 3, 2};
//        int[] nums = {0,3,7,2,5,8,4,6,0,1};
        int[] nums = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};
        Solution solution = new LongestConsecutiveSequence().new Solution();
        System.out.println(solution.longestConsecutive(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我们静下来思考，这道题，说要找连续数字，
         * 连续数字有什么特点呢？
         * 我首先想到的是连续性，如果这个数字是连续的，
         * <p>
         * 那么怎么判断是否跳过呢？
         * 由于我们要枚举的数 xx 一定是在数组中不存在前驱数 x-1x−1 的，
         * 不然按照上面的分析我们会从 x-1x−1 开始尝试匹配，
         * 因此我们每次在哈希表中检查是否存在 x-1x−1 即能判断是否需要跳过了
         *
         * @param nums
         * @return
         */
        public int longestConsecutive(int[] nums) {

            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                set.add(nums[i]);
            }


            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                if (!set.contains(nums[i] - 1)) {
                    int temp = nums[i];
                    int count = 0;
                    while (set.contains(temp)) {
                        temp++;
                        count++;
                    }
                    ret = Math.max(ret, count);
                }
            }
            return ret;

        }

        /**
         * 排序，去做，但是题目说on的时间复杂度，就很方。
         *
         * @param nums
         * @return
         */
        public int longestConsecutive01(int[] nums) {
            if (nums.length <= 1) {
                return nums.length;
            }
            Arrays.sort(nums);

            int ret = 0;
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i - 1] + 1 == nums[i]) {
                    count++;
                } else if (nums[i - 1] + 1 < nums[i]) {
                    ret = Math.max(ret, count);
                    count = 1;
                }
            }
            return Math.max(ret, count);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
